<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8"/>
<title>Javascript implementation of Steven Fortune's algorithm to compute Voronoi diagrams: Demo 1</title>
<meta name="Keywords" lang="en" content="voronoi, fortune, javascript, raymond hill"/>
<!--[if lte IE 8]><script type="text/javascript" src="excanvas/excanvas.compiled.js"></script><![endif]-->
<script type="text/javascript" src="rhill-voronoi-core.min.js"></script>
<style type="text/css">
body {font-family:tahoma,verdana,arial;font-size:13px;margin:0;padding:0}
body > div {margin-left:4px;margin-right:4px;}
body > div > div {margin:0;border:1px solid #ccc;border-top:0;padding:4px;}
h1 {margin:0 0 0.5em 0;padding: 4px 5em 4px 4px;font:bold large sans-serif;background-color:#c9d7f1;}
h4 {font-size:14px;margin:0.5em 0 0 0;border:0;border-bottom:solid 1px #c9d7f1;padding:2px;background-color:#e5ecf9;}
#canvasParent {margin-top:0;margin-bottom:1em;padding:0;border:0}
#voronoiCode {font:11px monospace;overflow:auto;color:#666;}
#voronoiCode span {color:green;font-weight:bold;}
</style>
<script id="script" type="text/javascript">
var VoronoiDemo = {
    voronoi: new Voronoi(),
    sites: [],
    diagram: null,
    margin: 0.15,
    canvas: null,
    bbox: {xl:0,xr:800,yt:0,yb:600},
    benchmarkTimer: null,
    benchmarkTimes: new Array(50),
    benchmarkPointer: 0,
    benchmarkMaxSites: 100,

    init: function() {
        this.canvas = document.getElementById('voronoiCanvas');
        this.randomSites(100,true);
        this.render();
        },

    benchmarkToggle: function() {
        if ( this.benchmarkTimer ) {
            this.benchmarkStop();
            }
        else {
            this.benchmarkStart();
            }
        },

    benchmarkStart: function() {
        this.benchmarkMaxSites = Math.floor(parseFloat(document.getElementById('voronoiNumberSites').value));
        this.benchmarkPointer = 0;
        this.benchmarkTimer = setTimeout(this.benchmarkDo, 250);
        document.getElementById('voronoiBenchmark').value = 'Stop';
        },

    benchmarkDo: function() {
        var vd = VoronoiDemo;
        vd.randomSites(vd.benchmarkMaxSites, true);
        vd.render();
        vd.benchmarkTimes[vd.benchmarkPointer] = vd.diagram.execTime;
        vd.benchmarkPointer++;
        if ( vd.benchmarkPointer < vd.benchmarkTimes.length ) {
            document.getElementById('benchmarkResult').innerHTML = new Array(vd.benchmarkTimes.length-vd.benchmarkPointer+1).join('.');
            vd.benchmarkTimer = setTimeout(vd.benchmarkDo, 250);
            }
        else {
            vd.benchmarkStop();
            }
        },

    benchmarkStop: function() {
        if ( this.benchmarkTimer ) {
            clearTimeout(this.benchmarkTimer);
            this.benchmarkTimer = null;
            }
        var sum = 0;
        var fastest = Number.MAX_VALUE;
        var slowest = -Number.MAX_VALUE;
        this.benchmarkTimes.map(function(v){
            sum += v;
            fastest = Math.min(v, fastest);
            slowest = Math.max(v, slowest);
            });
        sum -= fastest;
        sum -= slowest;
        var avg = sum / (this.benchmarkPointer-2);
        document.getElementById('benchmarkResult').innerHTML =
            'average exec time for ' +
            this.benchmarkMaxSites +
            ' sites = ' +
            avg.toFixed(1) + ' ms ' +
            ' (' + (avg*1000/this.benchmarkMaxSites).toFixed(1) + ' µs/site)' +
            ', fastest = ' + fastest + ' ms, slowest = ' + slowest + ' ms.'
            ;
        document.getElementById('voronoiBenchmark').value = 'Benchmark';
        },

    clearSites: function() {
        this.sites = [];
        this.diagram = this.voronoi.compute(this.sites, this.bbox);
        this.updateStats();
        },

    randomSites: function(n,clear) {
        if (clear) {this.sites = [];}
        // create vertices
        var xmargin = this.canvas.width*this.margin,
            ymargin = this.canvas.height*this.margin,
            xo = xmargin,
            dx = this.canvas.width-xmargin*2,
            yo = ymargin,
            dy = this.canvas.height-ymargin*2;
        for (var i=0; i<n; i++) {
            this.sites.push({
                x: xo + Math.random()*dx + Math.random()/dx,
                y: yo + Math.random()*dy + Math.random()/dy
                });
            }
        this.voronoi.recycle(this.diagram);
        this.diagram = this.voronoi.compute(this.sites, this.bbox);
        this.updateStats();
        },

    recompute: function() {
        this.diagram = this.voronoi.compute(this.sites, this.bbox);
        this.updateStats();
        },

    updateStats: function() {
        if (!this.diagram) {return;}
        var e = document.getElementById('voronoiStats');
        if (!e) {return;}
        e.innerHTML = '('+this.diagram.cells.length+' Voronoi cells computed from '+this.diagram.cells.length+' Voronoi sites in '+this.diagram.execTime+' ms &ndash; rendering <i>not</i> included)';
        },

    render: function() {
        var ctx = this.canvas.getContext('2d');
        // background
        ctx.globalAlpha = 1;
        ctx.beginPath();
        ctx.rect(0,0,this.canvas.width,this.canvas.height);
        ctx.fillStyle = 'white';
        ctx.fill();
        ctx.strokeStyle = '#888';
        ctx.stroke();
        // voronoi
        if (!this.diagram) {return;}
        // edges
        ctx.beginPath();
        ctx.strokeStyle = '#000';
        var edges = this.diagram.edges,
            iEdge = edges.length,
            edge, v;
        while (iEdge--) {
            edge = edges[iEdge];
            v = edge.va;
            ctx.moveTo(v.x,v.y);
            v = edge.vb;
            ctx.lineTo(v.x,v.y);
            }
        ctx.stroke();
        // edges
        ctx.beginPath();
        ctx.fillStyle = 'red';
        var vertices = this.diagram.vertices,
            iVertex = vertices.length;
        while (iVertex--) {
            v = vertices[iVertex];
            ctx.rect(v.x-1,v.y-1,3,3);
            }
        ctx.fill();
        // sites
        ctx.beginPath();
        ctx.fillStyle = '#44f';
        var sites = this.sites,
            iSite = sites.length;
        while (iSite--) {
            v = sites[iSite];
            ctx.rect(v.x-2/3,v.y-2/3,2,2);
            }
        ctx.fill();
        },
    };
</script>
</head>
<body onload="VoronoiDemo.init();">
<a href="https://github.com/gorhill/Javascript-Voronoi"><img style="position: absolute; top: 0; right: 0; border: 0;" src="https://s3.amazonaws.com/github/ribbons/forkme_right_red_aa0000.png" alt="Fork me on GitHub"></a>
<h1>Javascript implementation of Steven Fortune's algorithm to compute Voronoi diagrams<br/>Demo 1: measuring peformance</h1>
<div id="divroot" style="width:800px;">
<p style="margin-top:0;margin-bottom:0"><a href="/voronoi/rhill-voronoi.html">&lt; Back to main page</a><ul style="margin-top:0">
<li><b>Demo 1: measuring peformance</b>
<li><a href="rhill-voronoi-demo2.html">Demo 2: a bit of interactivity</a>
<li><a href="rhill-voronoi-demo3.php">Demo 3: Fancy tiling</a>
<li><a href="rhill-voronoi-demo4.html">Demo 4: Looking up a Voronoi cell using a quadtree</a>
<li><a href="rhill-voronoi-demo5.html">Demo 5: Lloyd's relaxation</a>
<li><a href="http://www.raymondhill.net/blog/?p=458#comments">Comments</a>
</ul></p>
<h4 class="divhdr">Sites generator</h4>
<div class="divinfo" id="voronoiGenerator">
<input type="button" value="Generate" onclick="VoronoiDemo.randomSites(parseInt(document.getElementById('voronoiNumberSites').value,10),true);VoronoiDemo.render();"/> or <input type="button" value="Add" onclick="VoronoiDemo.randomSites(parseInt(document.getElementById('voronoiNumberSites').value,10),false);VoronoiDemo.render();"/><input id="voronoiNumberSites" type="text" value="100" size="5" maxlength="5"/> sites randomly (Warning: performance might suffer the more sites you add.)
<br/><input id="voronoiClearSites" type="button" value="Clear all sites" onclick="VoronoiDemo.clearSites();VoronoiDemo.render();"/>
<br/><input id="voronoiBenchmark" type="button" value="Benchmark" onclick="VoronoiDemo.benchmarkToggle();" /> Result: <span id="benchmarkResult">?</span>
</div>
<h4 class="divhdr">Canvas <span id="voronoiStats" style="font:normal 11px sans"></span></h4>
<div id="canvasParent">
<noscript>You need to enable Javascript in your browser for this page to display properly.</noscript>
<canvas id="voronoiCanvas" width="800" height="600" onclick="VoronoiDemo.recompute();"></canvas>
<div id="voronoiNoCanvasAlert" style="display:none;padding:1em;background-color:#fcc;color:black;">
<p>Your browser doesn't support the HTML5 &lt;canvas&gt; element technology.</p>
<p>See <a target="_blank" href="http://en.wikipedia.org/wiki/Canvas_(HTML_element)">Wikipedia</a> for information on which browsers support the <u>HTML5 &lt;canvas&gt;</u> technology.</p>
</div>
</div>
<h4 class="divhdr">Javascript source code for this page</h4>
<div class="divinfo" id="voronoiCode">
<pre>
<span>&lt;script type=&quot;text/javascript&quot; src=&quot;<a href="rhill-voronoi-core.js" target="_blank">rhill-voronoi-core.js</a>&quot;&gt;&lt;/script&gt;</span>
...
<div id="scriptContainer"></div>
...
</pre>
</div>
</div>
<script>
(function(){
var srcElem = document.getElementById("script");
if (srcElem) {
    var dstElem = document.getElementById("scriptContainer");
    if (dstElem) {
        dstElem.innerText = srcElem.innerHTML;
        }
    }
})();
</script>
</body>
</html>
